Graphics Database Organization
Graphics database applications such as those used in CAD systems are traditionally organized on the basis of graphical object type, the order of graphical object creation, and the layer on which the graphical object exists. However, some of the most fundamental interactions with graphics databases require queries based on the spacial location of the graphical objects making up the database. Servicing such interactions under the paradigm of the prior art requires extensive searching through the underlying database, which is randomly organized vis-a-vis location-based queries. As the database becomes large, these queries exact a significant penalty on system performance, including noticeable delays in system response time. Thus, the typical graphics database organization does not lend itself to graphical object selection queries based on object location.
Important graphics database interactions requiring location-based queries include user selection of graphical objects appearing on a display screen and system selection of graphical objects located in a given region of a graphics space. Both of these types of interactions are discussed in more detail below.